'''
什么是列表查找
    从列表中查找指定元素
    输入：列表，待查找元素
    输出：元素下标，未找到返回none或-1
顺序查找
    也叫线性查找，从列表第一个遍历到最后一个
二分查找
'''

#顺序查找 时间复杂度 O（n）
def linear_search(li,val):
    for ind in range(len(li)):
        if li[ind] ==val:
            return ind

    return None

print(linear_search([1,2,3,4],4))

#二分查找 O（log  n）
def binary_search(li,val):
    left=0
    right=len(li)-1
    while left <=right:
        mid=left+right //2
        if li[mid]==val:
            return mid
        elif li[mid] < val:
            left=mid+1
        else:
            right=mid-1
    return None
